package main.leetcode.offer.secondround.from03to50;

import java.util.Arrays;

/** 38.字符串的排列 */
public class ex38 {
    private String[] res;

    public String[] permutation(String str) {
        res = new String[str.length()];
        if (str.isEmpty()) {
            return res;
        }
        boolean[] isVisited = new boolean[str.length()];
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        backTrack(chars, 0, isVisited, new StringBuilder());
        return res;
    }

    private void backTrack(char[] chars, int index, boolean[] isVisited, StringBuilder cur) {
        if (cur.length() == chars.length) {
            res[index] = cur.toString();
            return;
        }

        for (int i = 0; i < chars.length; ++i) {
            // `!isVisited[i - 1]` 是为了上一波被撤销选择的相同的元素，他的状态已经被重置
            if (isVisited[i] || i > 0 && chars[i] == chars[i - 1] && !isVisited[i - 1]) {
                continue;
            }
            isVisited[i] = true;
            cur.append(chars[i]);
            backTrack(chars, index + 1, isVisited, cur);
            cur.deleteCharAt(cur.length() - 1);
            isVisited[i] = false;
        }
    }
}
